package com.hfi.wangzhengalgorithm;

/**
 * @author ChangLiang
 * @date 2019/12/10
 */
public class TimeComplexity {

    /**
     * Time complexity: O(n)
     * Space complexity:O(1)
     *
     * best case time complexity: O(1)  在极端情况下
     * worst case time complexity: O(n)
     * average time complexity: O(n)
     *
     * 获取array[0,n-1]中出现x的最后的index
     * @param array
     * @param n
     * @param x
     * @return not found, return -1
     */
    public int find(int[] array, int n, int x) {
        int i = 0;
        int pos = -1;
        for (; i < n; ++i) {
            if (array[i] == x) {
                pos = i;
            }
        }
        return pos;
    }

    private int[] array = new int[2];

    public int[] getArray() {
        return array;
    }

    int len = 2;
    int i = 0;

    /**
     * best case time complexity: O(1)
     * worst case time complexity: O(n)
     * average time complexity: O(1)  1*(2n-1)*1/2n+n*1*1/2n
     * amortized time complexity: O(1) 每次O(1)操作，都会跟着2n-1次O(1)的插入操作 把O(n)均摊到2n-1次的O(1)上
     * @param element
     */
    public void add(int element) {
        if (i >= len) {
            int[] new_array = new int[len * 2];
            for (int j = 0; j < len; ++j) {
                new_array[j] = array[j];
            }
            array = new_array;
            len = len * 2;
        }
        array[i] = element;
        ++i;
    }
}
